package stringalgorithm

import "fmt"

/*
找到坏字符在模式串中的位置(有重复的，则是靠后的那个)
为了每次不用每次都查询，将pattern中的所有出现的字符在pattern中的位置记录到map表中。
*/
func generateBadCharTable(pattern []rune) map[rune]int {

	badCharTable := make(map[rune]int)
	for idx, ch := range pattern {
		badCharTable[ch] = idx
	}

	return badCharTable
}

func generateGoodStringTable(pattern []rune) (suffixPosTbl []int, prefixTbl []bool) {

	suffixPosTbl = make([]int, len(pattern))
	prefixTbl = make([]bool, len(pattern))

	var i int

	var patternLen = len(pattern)
	for i = 0; i < patternLen; i++ {
		suffixPosTbl[i] = -1
		prefixTbl[i] = false
	}

	//对于每一段以prefixLen结束的prefix,去匹配所有长度的后缀（如果长度为1的suffix匹配的情况下，才有可能匹配长度为2的suffix）
	var prefixLen int
	//prefix 不能是整个字符串
	for prefixLen = 0; prefixLen < patternLen-1; prefixLen++ {

		prefixPos := prefixLen
		currSuffixlen := 0

		//从prefixLen开始往前匹配是否与后缀匹配(最多可以匹配prefixLen长度的后缀)
		for prefixPos >= 0 &&
			pattern[prefixPos] == pattern[patternLen-1-currSuffixlen] { //如果跟后缀匹配，则继续往前匹配
			//保证不出界

			suffixPosTbl[currSuffixlen] = prefixPos //记录下后缀在pattern中的位置（后缀只需要用长度表示就可以了)
			prefixPos--
			currSuffixlen++

		}

		if prefixPos < 0 {
			prefixTbl[currSuffixlen] = true
		}
	}

	return
}

func generateGoodStringTable2(pattern []rune) (suffixPosTbl []int, prefixTbl []bool) {

	suffixPosTbl = make([]int, len(pattern))
	prefixTbl = make([]bool, len(pattern))

	var i int

	var patternLen = len(pattern)
	for i = 0; i < patternLen; i++ {
		suffixPosTbl[i] = -1
		prefixTbl[i] = false
	}

	for suffixLen := 1; suffixLen <= patternLen-1; suffixLen++ {
		//try find the suffix in the prefix
		for prefixLen := suffixLen; prefixLen <= patternLen-1; prefixLen++ {
			var startPos int
			for startPos = 0; startPos < suffixLen; startPos++ {
				if pattern[prefixLen-startPos-1] != pattern[patternLen-1-startPos] {
					break
				}
			}

			if startPos == suffixLen {
				suffixPosTbl[suffixLen-1] = prefixLen - startPos
				if prefixLen == suffixLen {
					prefixTbl[suffixLen-1] = true
				}
			}

		}
	}

	return
}

func FindPatternInStr_BM(str []rune, pattern []rune) {
	badCharTbl := generateBadCharTable(pattern)
	suffixPosTbl, hasPrefixTbl := generateGoodStringTable(pattern)

	strLen := len(str)
	patternLen := len(pattern)
	var startPos int = 0
	for startPos < strLen-patternLen+1 {
		//从后往前匹配
		var idx int
		for idx = patternLen - 1; idx >= 0; idx-- {
			if pattern[idx] != str[startPos+idx] {
				break
			}
		}
		if idx < 0 {
			fmt.Printf("find pattern in str :%d \n", startPos)
			startPos += patternLen
		} else {
			posInPattern, ok := badCharTbl[str[startPos+idx]]
			if !ok {
				posInPattern = -1
			}
			badCharMoveLen := idx - posInPattern
			var finalMoveLen int = badCharMoveLen
			if idx < patternLen-1 {
				//this means it has good suffix
				//suffix len is patternLen - 1 - idx
				goodSuffixLen := patternLen - 1 - idx
				suffixPos := suffixPosTbl[goodSuffixLen]
				if suffixPos == -1 {
					for i := goodSuffixLen - 1; i >= 0; i-- {
						isPrefix := hasPrefixTbl[i]
						if isPrefix {
							suffixPos = i
							break
						}
					}
				}
				goodSuffixMoveLen := patternLen - 1 - suffixPos
				if finalMoveLen < goodSuffixMoveLen {
					finalMoveLen = goodSuffixMoveLen
				}
			}
			startPos += finalMoveLen
		}
	}
}
